In the field of high-speed packet processing, there is a renewed interest in developing memory-efficient data structures for packet processing functions, such as for performing longest IP prefix matching for IP packet forwarding. This renewed interest is motivated by several factors that necessitate the use of memory-efficient data structures. First, the expected transition to 100 Gbps interfaces requires the use of memory-efficient data structures in order to achieve good performance while minimizing high-speed memory costs. Second, growth of forwarding table sizes and the need to forward IPv6 packets both increase the importance of achieving high efficiencies in memory usage. Third, multi-core processors are increasingly being employed for performing packet forwarding and, in systems using such multi-core processors, good performance is achieved by storing entire packet forwarding data structures in on-chip caches, which requires the use of highly memory-efficient data structures. Finally, the growing use of network virtualization, in which a physical router may operate as multiple virtual routers and each of the multiple virtual routers maintains a copy of the forwarding data structures, requires use of memory-efficient data structures by each of the multiple virtual routers. Disadvantageously, however, the existing longest IP prefix matching schemes all tend to consume a large amount of memory and, therefore, are not suitable for use in satisfying the factors described above.